/// @tags: MoDuiwithModify
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  int ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

int const N = 1e5 + 4e4, B = 4609, M = 1e6 + 5;

int cur;
int a[N], ans[N], buk[M];

struct Event {
  int pos, ori, col;
} eve[N];

struct Query {
  int l, r, t, id, bel, rbel;

  inline bool operator<(Query const &rhs) const {
    return bel == rhs.bel ? (rbel == rhs.rbel ? t < rhs.t : ((bel & 1) ^ (rbel < rhs.rbel)))
                          : bel < rhs.bel;
  }
} q[N];

inline void add(int x) { cur += !buk[a[x]]++; }

inline void del(int x) { cur -= !--buk[a[x]]; }

inline int main() {
  int n, m, q_cnt = 0, m_cnt = 0, L = 1, R = 0, T = 0;
  read(n), read(m);
  for (int i = 1; i <= n; ++i) read(a[i]);
  char opt[2];
  for (int i = 1; i <= m; ++i) {
    scanf("%s", opt);
    switch (opt[0]) {
      case 'Q':
        ++q_cnt;
        read(q[q_cnt].l), read(q[q_cnt].r);
        q[q_cnt].t = m_cnt, q[q_cnt].bel = q[q_cnt].l / B, q[q_cnt].id = q_cnt;
        q[q_cnt].rbel = q[q_cnt].r / B;
        break;
      case 'R':
        ++m_cnt;
        read(eve[m_cnt].pos), read(eve[m_cnt].col);
        eve[m_cnt].ori = a[eve[m_cnt].pos];
        a[eve[m_cnt].pos] = eve[m_cnt].col;
    }
  }
  for (int i = m_cnt; i >= 1; --i) a[eve[i].pos] = eve[i].ori;  // 还原
  sort(q + 1, q + q_cnt + 1);
  for (int i = 1; i <= m; ++i) {
    while (q[i].r > R) add(++R);
    while (q[i].l < L) add(--L);
    while (q[i].r < R) del(R--);
    while (q[i].l > L) del(L++);
    while (q[i].t < T) {
      int pos = eve[T].pos;
      if (L <= pos && pos <= R) del(pos);
      a[pos] = eve[T--].ori;
      if (L <= pos && pos <= R) add(pos);
    };
    while (q[i].t > T) {
      int pos = eve[++T].pos;
      if (L <= pos && pos <= R) del(pos);
      a[pos] = eve[T].col;
      if (L <= pos && pos <= R) add(pos);
    };
    ans[q[i].id] = cur;
  }
  for (int i = 1; i <= q_cnt; ++i) printf("%d\n", ans[i]);
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P1903 [国家集训队] 数颜色 | 维护队列.in", "r", stdin);
  freopen("P1903 [国家集训队] 数颜色 | 维护队列.out", "w", stdout);
#endif
#endif

  return BlueQuantum::main();
}